1826E - Walk the Runway - CodeForces Solution

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
using namespace chrono;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// #define ordered_set tree<pair <int,int>, null_type,less<pair <int,int> >, rb_tree_tag,tree_order_statistics_node_update>
//less_equal--> multiset| greater--> dec order
// #define ordered_set tree<int, null_type,less_equal<int >, rb_tree_tag,tree_order_statistics_node_update>

#define all(x) x.begin(),x.end()
#define ff first
#define ss  second
#define pb push_back
#define PI 3.141592653589793238462
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define YES  cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
typedef long long int ll;
typedef vector <int> vi;
typedef vector <long long> vll;
typedef vector <vector <int> > vvi;
typedef vector <vector <long long> > vvll;
typedef vector <pair <int,int> > vpii;
typedef vector <pair <long long,long long> > vpll;
typedef pair <int,int> pii;
typedef pair <long long, long long> pll;
const double pi = 3.1415926535;
const int INF = 1e9;
const ll bigmod = 100055128505716009;
// __print() functions
void __print(int x) {cerr<<x; }
void __print(long long x) { cerr<<x; }
void __print(string x){ cerr<<x; }
void __print(char x){ cerr<<x; }
void __print(bool x){ cerr<<x; }
void __print(double x){ cerr<<x; }


// printing complex datatypes
template <class T> void __print(vector <T> v){ cerr<<"[ "; for(T i:v){ __print(i);cerr<<" "; } cerr<<"]"; }
template <class T, class V> void __print(pair <T,V> p){ cerr <<"{ "; __print(p.first);cerr<<" , ";__print(p.second);cerr<<" }";} 
template <class T> void __print(set <T> v) {cerr << "[ "; for (T i : v) {__print(i); cerr << " ";} cerr << "]";}
template <class T> void __print(multiset <T> v) {cerr << "[ "; for (T i : v) {__print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void __print(map <T, V> v) {cerr << "[ "; for (auto i : v) {__print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void __print(vector <pair <T, V> > v){cerr << "[ "; for(auto i: v){__print(i); cerr<<" ";} cerr<<"]";}
template <class T> void __print(vector <vector <T> > v){ cerr<<endl<<endl; for( auto i:v){ for(T j:i){ cerr<<j<<" ";} cerr<<endl; } cerr<<endl<<endl;}


#ifndef ONLINE_JUDGE
    #define debug(x) cerr<< "Line " << __LINE__ << " : " <<#x<<" --> ";__print(x);cerr<<endl; 
#else
    #define debug(x) 
#endif

// Random number generator
uint64_t random_address() { char *p = new char; delete p; return uint64_t(p); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1));
// just use rng()

//functions-------------------------------------------------------------------------------------------------------------------------
void google(int t) {cout << "Case #" << t << ": ";}
ll binpower(ll a, ll b, ll m){ ll res =1; while(b>0){ if(b&1) res = res*a%m;a = a*a%m;b = b>>1; }   return res;}
int ext_gcd(int a,int b){if(!a || !b) return a|b; int shift = __builtin_ctz(a|b); a = a>>__builtin_ctz(a);do{ b= b>>__builtin_ctz(b);if(a>b){ swap(a,b);} b-=a; }while(b);return a<<=shift;}
void precision(int a) {cout << setprecision(a) << fixed;}
ll mminvprime(ll a,ll p){return binpower(a,p-2,p);}
int popcount(int x){ return __builtin_popcount(x);}

// const int mod =998244353;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
const int N2 = 2500;
const int MAXN = 2e5 + 6;
// ---------------------------------------------------------------------------------------------------------------------------------

// the main point here is the use of bitsets
using bs = bitset <5000>;
void solve(){
    int m,n; cin>>m>>n;
    vll p(n);
    for(auto &i : p) cin>>i;
    bs mask;
    for(int i =0;i<5000; i++) mask[i] = true;
    vector <bs> vec(n, mask);
    
    vvll store(m, vll(n));
    vi ind(n);
    iota(all(ind), 0);
    for(int i =0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>store[i][j];
        }

        
        sort(all(ind), [&](int a, int b){return store[i][a] < store[i][b];});
        bs tillnow;
        for(int j =0;j<n;j++){
            int k = j;
            while(k < n && store[i][ind[k]] == store[i][ind[j]]){
                vec[ind[k]] &= tillnow;
                k++;
            }

            debug(j);
            debug(k);
            debug(ind);
            while(j < k){
                // cerr<<"bef"<<" "<<tillnow<<endl;
                tillnow[ind[j]] = true;
                j++;
                // cerr<<"aft"<<" "<<tillnow<<endl;
            }
            

            j--;
        }
    }
    // now we got for every dancer i --> the number of dancers it can follow
    // note this will need to follow the last order && this is not circular because of strict <
    // so we can directly use a dp withouot comparing
    
    debug(ind);
    vll dp= p;
    for(auto i : ind){
        for(int j =0;j<5000; j++){
            if(vec[i][j] == true)
                dp[i] = max(dp[i], dp[j] + p[i]);
        }
    }

    cout<<*max_element(all(dp))<<endl;

}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);   
    freopen("error.txt","w",stderr);
    #endif          
    fastio();       
    auto start1 = high_resolution_clock::now();
    solve();
    auto end1=  high_resolution_clock::now();
    double duration = duration_cast<nanoseconds>(end1 - start1).count();
    duration *= 1e-9;

    #ifndef ONLINE_JUDGE
        cerr<<"Time - "<<fixed<<duration<<setprecision(9) <<" s"<<endl;
    #endif

}


// string((int)len, '0')